package 排序;

/**
 * 【大顶堆】
 * 堆中某个节点的值总是大于等于其子节点的值，并且堆是一颗完全二叉树。
 *
 * 堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。
 * 位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。
 * @param <T>
 */
public class 堆<T extends Comparable<T>> {

    private T[] heap;
    private int N = 0;

    public 堆(int maxN) {
        this.heap = (T[]) new Comparable[maxN + 1];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    private boolean less(int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }

    private void swap(int i, int j) {
        T t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }

    // 上浮：把大元素向上排
    private void swim(int k) {
        // k 的父节点 k/2 更小的时候需要对 k 做上浮操作
        while (k > 1 && less(k / 2, k)) {
            swap(k / 2, k);// 交换
            k = k / 2;// 更改当前 k 的位置
        }
    }
    // 下沉：把小元素往下排
    private void sink(int k) {
        // k 的子节点分别是 k*2 与 k*2+1
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(j, j + 1))// 左子节点要小于右子节点
                j++;
            // 若父节点 >= 左子节点 就表示
            if (!less(k, j))
                break;
            // 父节点 < 左子节点，就需要交换
            swap(k, j);

            k = j;
        }
    }

    // 插入元素:将新元素放到数组末尾，然后上浮到合适的位置。
    public void insert(T v) {
        heap[++N] = v;
        swim(N);
    }

    // 删除最大元素:
    // 从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。
    public T delMax() {
        T max = heap[1];
        swap(1, N--);
        heap[N + 1] = null;
        sink(1);
        return max;
    }
}
